1. Technical Field
The present invention relates generally to systems for processing routing and filtering information for each packet received at a router node of a data transmission network, and in particular to an interleaved processing system based upon a tree lookup structure in a network router.
2. Description of the Related Art
Today, data communication systems are based upon data transmission networks wherein routers are used to link remote sites. Routing is a major bottleneck in such systems primarily due to the overhead processing time and the additional memory capacity required for routing. One of the primary routing functions entails determining a particular routing path for a packet or frame across the network using specific protocols. This path determination is based on a variety of metrics such as the delay introduced by the network or the link cost. In addition, this determination takes into account other rules generically called filtering, such as communication restrictions or priority criteria.
Another important routing function is packet forwarding which entails processing of inbound data packets and the subsequent forwarding of these data packets to the appropriate outbound destination in accordance with a destination address within the packet header.
Both the determination of the routing path and packet forwarding based upon the destination address field in the packet header, are performed within the same routing device. Nevertheless, new techniques tend to exploit the difference between these functions, thus separating the corresponding operations. For example, a single routing path processing unit could support several packet forwarding units.
Since the routing processing time is relatively high and varies from one routing computation to another, it is difficult to support multiple time sensitive applications such as multimedia. For both the filtering and packet forwarding processing, memory searches consume considerable time. Within the routing processing context, “searching” entails retrieving routing information encoded within a predetermined bit pattern of an packet address header. In particular, the destination of a data packet typically corresponds to such a bit pattern within the destination address field of the packet header. The required search involves comparing a portion of the destination address bit pattern to a predetermined bits sequence, or “keys”, that identify appropriate routing information. Efforts have been made to optimize the speed of such comparison based searches (often referred to as prefix matching searches) by using parallel processing, but this method admits its own limitations.
In addition to packet forwarding, a typical packet routing cycle includes a filtering process that is performed with respect to a source address field in the packet header. Today, the routing process and the filtering process are either performed sequentially utilizing a single processing entity, or are performed simultaneously utilizing two separate processing units. For each process, there are two phases which are repeated until the end of the process. These processes are typically referred to as an instruction loading phase and an instruction processing phase. It should be noted that, in classical systems, the loading and processing phases are very close in duration.
The routing function for determining an outgoing destination node to which a packet will be forwarded, typically utilizes a longest prefix matching (LPM) algorithm that is generally implemented in a tree structure. The filtering process may also utilize this same type of process and algorithm but in a separate tree structure. The trees utilized for routing and filtering are implemented in a memory structure containing an instruction at each tree node, wherein each instruction provides a link to sub-nodes. The tree structure is thus traversed starting from a tree root down to a leaf node that contains an instruction which provides either the routing information or the filtering rules. This last instruction is very often provided in an indirect manner such as by an address value that corresponds to the field that contains the routing, or by filtering information for each leaf node. For further information regarding the nature of LPM searching, reference is made to the article “Routing on longest-matching prefixes”, IEEE/ACM transactions on networking, vol. 4, n—1, February 1996, pages 86-97 which is incorporated herein by reference.
Systems currently available for processing the routing function or the filtering function using a tree structure require considerable memory overhead for storing the information in each node, and also consume considerable processing overhead for the requisite large number of memory accesses. From the foregoing, it can be appreciated that a need exists for a processing system that enables an optimized the processing system and method for performing both routing and filtering functions within a router.